package main

import "fmt"

//不完善，后面参照java代码修改
/**
 * @param edge: edge[i][0] [1] [2]  start point,end point,value
 * @return: return the second diameter length of the tree
 */
func GetSecondDiameter(edge [][]int) int64 {
	n := len(edge)
	g := buildGraph(n+1, edge)
	fmt.Println(g)
	path1 := bfs(0, g)
	path2 := bfs(path1.Data, g)
	path3 := bfs(path2.Data, g)

	ans := path2.Distance
	if ans < path3.Distance {
		ans = path3.Distance
	}
	return int64(ans)
}

func bfs(root int, g map[int][]Node) Node {
	q := []int{}
	q = append(q, root)
	first := root
	second := root
	disToRoot := map[int]int{}

	disToRoot[root] = 0

	for len(q) > 0 {
		qnew := []int{}
		size := len(q)
		for i := 0; i < size; i++ {
			cur := q[i]
			nexts := g[cur]

			for _, next := range nexts {
				_, ok := disToRoot[next.Data]
				if ok {
					continue
				}

				distance := disToRoot[cur] + next.Distance
				fmt.Println("distance:", distance)
				if distance > disToRoot[first] {
					second = first
					first = next.Distance
				} else if distance > disToRoot[second] {
					second = next.Data
				}

				disToRoot[next.Data] = distance
				qnew = append(qnew, next.Data)
			}
		}

		q = qnew
	}

	fmt.Println("first=", first, " distance:", disToRoot[second])
	return Node{Data: first, Distance: disToRoot[second]}
}

func buildGraph(n int, edge [][]int) map[int][]Node {
	g := map[int][]Node{}
	for i := 0; i < n; i++ {
		g[i] = []Node{}
	}

	for _, v := range edge {
		a := v[0]
		b := v[1]
		c := v[2]
		g[a] = append(g[a], Node{Data: b, Distance: c})
		g[b] = append(g[b], Node{Data: a, Distance: c})
	}
	return g
}

type Node struct {
	Data     int
	Distance int
}

func main() {
	fmt.Println(GetSecondDiameter([][]int{{0, 1, 4}, {0, 2, 7}}))
}

/*
LintCode-Logo
搜索题目、标签、题集
中文
avatar
您有217条未读消息，请及时查看
291 · 第二直径
算法
中等
通过率
41%

题目
题解8
笔记
讨论20
排名
记录
描述
给出由
n
n个结点，
n
−
1
n−1条边组成的一棵树。求这棵树的第二直径，也就是两两点对之间距离的次大值。
给出大小为
(
n
−
1
)
×
3
(n−1)×3的数组edge,edge[i][0],edge[i][1],edge[i][2],表示第i条边是从edge[i][0]连向edge[i][1]，长度为edge[i][2]的无向边。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


2
≤
n
≤
1
0
5
2≤n≤10
5


1
≤
e
d
g
e
[
i
]
[
2
]
≤
1
0
5
1≤edge[i][2]≤10
5


因为DFS(Depth-First-Search)容易爆栈，请使用BFS(Breadth First Search)完成该题目
如果有多个点对的距离都是最长，那么你只需要返回最长距离即可~

样例
输入:[[0,1,4],[0,2,7]]
输出:7
解释:两两之间的次大值为0到2的7

标签
推荐课程

简历/BQ/项目 面试软技能指导
FLAG高级工程师深度BQ辅导，简历打造+1V1模拟面试，反面试套路、高效上岸！
已开启智能提示
发起考试
30 分 00 秒
1234567

测试数据
提交结果
Accepted
100%
4240 ms
时间消耗
·
397.18 MB
空间消耗
·
您的提交打败了
45.84 %
的提交
查看详情与排名分布
贡献测试数据
和你的朋友们分享你的AC



发布题解，分享我的解题思路
控制台
历史提交

*/
